class Solution {
    // class BigHeap implements Comparator<Integer> {
    //     public int compare(Integer o1,Integer o2) {
    //         return o2.compareTo(o1);
    //     }
    // }


    // public int[] smallestK(int[] arr, int k) {
    //     int[] ret = new int[k];
    //     if(arr == null || k == 0) {
    //         return ret;
    //     }

    //     PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,new BigHeap());

    //     for(int i = 0;i < k;i++) {
    //         priorityQueue.offer(arr[i]);
    //     }

    //     for(int i = k;i < arr.length;i++) {
    //         int val = priorityQueue.peek();
    //         if(arr[i] < val) {
    //             priorityQueue.poll();
    //             priorityQueue.offer(arr[i]);
    //         }
    //     }

    //     for(int i = 0;i < k;i++) {
    //         ret[i] = priorityQueue.poll();
    //     }
    //     return ret;
    // }
    public int[] smallestK(int[] arr, int k) {
        qsort(arr,0,arr.length - 1,k);
        int[] ret = new int[k];
        for(int i = 0;i < k;i++)
            ret[i] = arr[i];

        return ret;
    }

    public void qsort(int[] nums,int l,int r,int k){
        if(l >= r) return;

        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1,right = r + 1,i = l;
        while(i < right) {
            if(nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }
        int a = left - l + 1,b = right - left - 1;
        if(a > k) qsort(nums,l,left,k);
        else if(a + b >= k) return;
        else qsort(nums,right,r,k - a - b);
    }

    public void swap(int[] nums,int i,int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

}
